package segment;

public class NumArray3 {
    private int[] data; // 存放原始数据
    private int[] sum; // sum[i]存储前i个元素的和, 即sum[i]存储num[0...i-1]的和, sum(i,j) = sum(j+1)-sum(i)

    public NumArray3(int[] nums) {

        data = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            data[i] = nums[i];

        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1; i < sum.length; i ++)
            sum[i] = sum[i-1] + nums[i-1];
    }

    public void update(int i, int val) {
        data[i] = val;
        for (int k = i+1; k < sum.length; k++)
            sum[k] = sum[k-1] + data[k-1];
    }

    public int sumRange(int i, int j) {
        return sum[j+1] - sum[i];
    }
}
